import java.util.Arrays;

public class TestHeap {
    private int[] elem;
    private int usedSize;

    public TestHeap() {
        this.elem = new int[10];
    }
    public void initHeap(int [] array){
        for (int i = 0; i < array.length; i++) {
            elem[i]=array[i];
            usedSize++;
        }
    }
    public void createHeap(){
        for (int parent =( usedSize-1-1)/2; parent >0 ; parent--) {
            shiftDown(parent,usedSize);
        }
    }
    public void shiftDown(int parent,int usedSize){//向下比较
        int child=2*parent+1;
        while (child<usedSize){
            if (child+1<usedSize &&elem[child]<elem[child+1]){
                child++;//child是左右子树最大值
            }
            if (elem[child]>elem[parent]){
                swap(child,parent);
                parent=child;
                child=2*parent+1;
            }else{
                break;
            }
        }
    }
    public void swap(int i,int j){
        int temp=elem[i];
        elem[i]=elem[j];
        elem[j]=temp;
    }
    public void offer(int val){
        if ((isFull())){
            this.elem= Arrays.copyOf(elem,2*elem.length);
        }
        elem [usedSize]=val;
        shiftUp(usedSize);
        usedSize++;

    }
    public void shiftUp(int child){
        int parent=(child-1)/2;
        while (child>0){
            if (elem[child]>elem[parent]){
                swap(child,parent);
                child=parent;
                parent=(child-1)/2;

            }else{
                break;
            }
        }
    }
    public boolean isFull(){
        return elem.length==usedSize;
    }
    public int poll(){
     int temp=elem[0] ;
     swap(0,usedSize-1);
     usedSize--;
     shiftDown(0,usedSize);
     return temp;
    }
    public void heapSort(){
        int end=usedSize-1;
        while (end>0) {
            swap(0, end);//堆排序
            shiftDown(0, end);
            end--;
        }
    }
}
